#include <iostream>

struct Node
{
  const std::string& label;
  Node* prev;
  Node* next;

  Node(const std::string& l)
    : label(l), prev(NULL), next(NULL)
  { }

  Node(const std::string& l, Node* p, Node* n)
    : label(l), prev(p), next(n)
  { }
};


std::ostream&
operator<< (std::ostream& os, const Node& node)
{
  os << node.label << "[me = " << &node << ", p = " << node.prev << ", n = " << node.next << "]";
  
  return os;
}


void
check_pass_pointer(Node* list)
{
  std::cout << "Check pass by pointer: list = " << list->label
	    << ", next = " << list->next->label << std::endl;
}

void
check_pass_pointer_ref(Node*& list)
{
  std::cout << "Check pass by pointer ref: list = " << list->label
	    << ", next = " << list->next->label << std::endl;
}

void
print_list(const Node* list)
{
  if (list == NULL)
    {
      std::cout << "[End of List]" << std::endl;
      return;
    }
  std::cout << list->label << " ";
  print_list(list->next);
}


// only here it makes a difference between passing list as a pointer
// and as a reference to a pointer!
void
push_back(Node*& list, Node* node)
{
  if (list == NULL)
    {
      list = node;
      list->next = NULL;
      list->prev = NULL;
    }
  else if (list->next == NULL)
    {
      list->next = node;
      node->prev = list;
    }
  else
    {
      push_back(list->next, node);
    }
}


Node*
node_at(Node* list, std::size_t pos)
{
  Node* tmp = list;
  std::size_t i = 0;
  
  while ((i < pos) && (tmp != NULL))
    {
      ++i;
      tmp = tmp->next;
    }

  return tmp;
}

void
swap(Node*& list, Node* node1, Node* node2)
{
  if (node1->prev != NULL) node1->prev->next = node2;
  if (node1->next != NULL) node1->next->prev = node2;
  if (node2->prev != NULL) node2->prev->next = node1;
  if (node2->next != NULL) node2->next->prev = node1;

  Node* tmp;
  tmp = node2->next; node2->next = node1->next; node1->next = tmp;
  tmp = node2->prev; node2->prev = node1->prev; node1->prev = tmp;

  if (node1->prev == NULL)
    {
      list = node1;
    }
  else if (node2->prev == NULL)
    {
      list = node2;
    }
}

int
main()
{
  // if I use char* languages[] and later create a new node as
  // Node(std::string(languages[i])) then I will get in the end a list
  // in which all nodes have the same label, since at each iteration
  // of the "for" loop, a new string object is created and is then
  // deleted in the next iteration (all happen at the same address).

  std::string languages[] = {"CPP", "Java", "Pascal", "Scala", "Delphi", "PHP", "ASP"};

  Node* list;
  for (int i = 0; i < 6; ++i)
    {
      Node* node = new Node(languages[i]);
      push_back(list, node);
    }

  print_list(list);

  Node* n0 = node_at(list, 0);
  Node* n2 = node_at(list, 2);
  Node* n3 = node_at(list, 3);
  Node* n4 = node_at(list, 4);
  Node* n5 = node_at(list, 5);

#ifdef DEBUG
  std::cout << "Before swapping:" << std::endl
	    << "n0: " << *n0 << std::endl
	    << "n2: " << *n2 << std::endl
	    << "n3: " << *n3 << std::endl
	    << "n4: " << *n4 << std::endl
	    << "n5: " << *n5 << std::endl;
#endif

  swap(list, n0, n3);
  //  list = n3;

#ifdef DEBUG
  std::cout << "After swapping:" << std::endl
	    << "n0: " << *n0 << std::endl
	    << "n2: " << *n2 << std::endl
	    << "n3: " << *n3 << std::endl
	    << "n4: " << *n4 << std::endl
	    << "n5: " << *n5 << std::endl;
#endif

  print_list(list);
}
